#pragma once

//Richard Small

//Singly Linked List

//Common functions and classes for an easier and faster singly linked list

/*
Note
All functions that go backwards in the list
will be significantly slower that going forwards
*/

//Declaring SLLIter so the list knows what it is
template <typename type> class SLLIter;

//List Decleration
template <typename type = int>
class SLList
{
	//making iterator class a friend;
	friend class SLLIter<type>;

	//node structure used for the list;
	struct node
	{
		type data;
		node* next;
	};

	//the head node of the list
	node* head;

	//easy identifier to find the size of the list;
	unsigned int size;

public:

	SLList(void);

	~SLList(void);

	SLList<type>& operator=(const SLList<type>& that);

	SLList(const SLList<type>& that);

	void addHead(const type& v);

	void addEnd(const type& v);

	void clear();

	void reverse();

	void stupidrecursivefunction(node* whatever);

	void insert(SLLIter<type>& index, const type& v);

	void remove(SLLIter<type>& index);

	void remove(type* obj);

	inline unsigned int getsize() const { return size; }
};

//constructor
template <typename type>
SLList<type>::SLList(void)
{
	head = 0;
	size = 0;
}

//destructor
template <typename type>
SLList<type>::~SLList(void)
{
	clear();
}

//recursive function used when copying
template <typename type>
void SLList<type>::stupidrecursivefunction(node* whatever)
{
	if(whatever)
	{
		stupidrecursivefunction(whatever->next);
		addHead(whatever->data);
	}
}

// = overload that copys a list
template <typename type>
SLList<type>& SLList<type>::operator=(const SLList<type>& that)
{
	if(this != &that)
	{
		clear();
		stupidrecursivefunction(that.head);
	}

	return *this;
}

// copy constructor that copys the list
template <typename type>
SLList<type>::SLList(const SLList<type>& that)
{
	head = 0;
	size = 0;
	stupidrecursivefunction(that.head);
}

//adds data from the user to the head of the list
template <typename type>
void SLList<type>::addHead(const type& v)
{
	node* temp = new node;

	temp->data = v;
	temp->next = head;

	head = temp;

	size++;
}

//adds data from the user to the end of the list
/*
****Warning****
Significnatly slower in large lists
*/
template <typename type>
void SLList<type>::addEnd(const type& v)
{
	if(!head)
	{
		addHead(v);
	}
	else
	{
		node* curr = head;

		while(curr->next)
		{
			curr = curr->next;
		}

		curr->next = new node;

		curr->next->data = v;
		curr->next->next = 0;

		size++;
	}
}

//clears the list of all memory and data
template <typename type>
void SLList<type>::clear()
{
	node* temp;

	while(head)
	{
		temp = head;
		head = head->next;
		delete temp;
	}

	head = 0;
	size = 0;
}

//Inserts data from the user at specified iterator location
template <typename type>
void SLList<type>::insert(SLLIter<type>& index, const type& v)
{
	if(index.prev)
	{
		node* temp = new node;
		temp->data = v;
		index.prev->next = temp;
		temp->next = index.onThisNode;
		index.onThisNode = temp;
		size++;
	}
	else if (index.onThisNode)
	{
		node* temp = new node;
		temp->data = v;
		temp->next = head;
		head = temp;
		index.onThisNode = head;
		size++;
	}
}

//Removes data from the list at specified user location
template <typename type>
void SLList<type>::remove(SLLIter<type>& index)
{
	if(index.prev && index.onThisNode)
	{
		index.prev->next = index.onThisNode->next;
		delete index.onThisNode;
		index.onThisNode = index.prev->next;
		size--;
	}
	else if (index.onThisNode)
	{
		node* temp = index.onThisNode;
		index.onThisNode = index.onThisNode->next;
		head = index.onThisNode;
		delete temp;
		size--;
	}
}

//Reverses the entire list
template <typename type>
void SLList<type>::reverse()
{
	node* newList = NULL;
	node* current = head;

	while (current)
	{
		node* next = current->next;
		current->next = newList;
		newList = current;
		current = next;
	}

	head = newList;
}

//Decleration of the iterator used with the list
template <typename type = int>
class SLLIter
{
	//making list class a friend
	friend class SLList<type>;

	//Holds the current list being iterated
	SLList<type>* list;

	//Prev and Current node the iterator is on
	typename SLList<type>::node* prev;
	typename SLList<type>::node* onThisNode;

public:

	SLLIter(SLList<type>& listToIterate);

	void begin();

	void end();

	bool checkifvalid() const;

	SLLIter<type>& operator++();

	SLLIter<type>& operator--();

	type& current() const;
};

//Constructor
template <typename type>
SLLIter<type>::SLLIter(SLList<type>& listToIterate)
{
	list = &listToIterate;
	onThisNode = list->head;
	prev = 0;
}

//Puts Prev and Current node at the head of the list
template <typename type>
void SLLIter<type>::begin()
{
	onThisNode = list->head;
	prev = 0;
}

//Puts Prev and Current node at the end of the list
/*
****Warning****
Significnatly slower in large lists
*/
template <typename type>
void SLLIter<type>::end()
{
	onThisNode = list->head;
	prev = 0;

	if(onThisNode)
	{
		while(onThisNode->next)
		{
			prev = onThisNode;
			onThisNode = onThisNode->next;
		}
	}
}

//Checks if the iterator is at a valid node of the list
template <typename type>
bool SLLIter<type>::checkifvalid() const
{
	if(onThisNode)
		return false;
	else
		return true;
}

//Moves the iterator one node forwards
template <typename type>
SLLIter<type>& SLLIter<type>::operator++()
{
	if(onThisNode)
	{
		prev = onThisNode;
		onThisNode = onThisNode->next;
	}

	return *this;
}

//Moves the iterator one node backwards
/*
****Warning****
Significnatly slower in large lists
*/
template <typename type>
SLLIter<type>& SLLIter<type>::operator--()
{
	if(prev)
	{
		typename SLList<type>::node* getprev = list->head;

		if(getprev != prev)
		{
			while(getprev->next != prev)
			{
				getprev = getprev->next;
			}
		}
		else
			getprev = 0;

		onThisNode = prev;
		prev = getprev;
	}
	else if(onThisNode)
	{
		onThisNode = 0;
	}

	return *this;
}

//returns the data at Current node to the user
template <typename type>
type& SLLIter<type>::current() const
{
	return onThisNode->data;
}

